package util;

import geom.Geometry;

import java.util.Iterator;
import java.util.LinkedList;

import render.Plane;
import render.Primitive;
import render.RaytracerImage;

public class KDNode {
	LinkedList<Primitive> primitives;
	KDNode front;
	KDNode back;
	
	int axis;
	double d;
	
	private KDNode(LinkedList<Primitive> primitives, KDNode front, KDNode back, int axis, double d) {
		this.primitives = primitives;
		this.front = front;
		this.back = back;
		
		this.axis = axis;
		this.d = d;
	}
	
	public boolean isleaf() {
		return primitives != null;
	}

	public static KDNode createKDTree(LinkedList<Primitive> primitives, int depth) {
		int axis = depth % 3;
		LinkedList<Primitive> front = new LinkedList<Primitive>();
		LinkedList<Primitive> back = new LinkedList<Primitive>();
		Primitive primitive;

		Primitive.Postion pos;		
		
		if(primitives.size() <= 100 || depth == 20) {
//			System.out.println("size: "+pr.size()+" depth: "+depth);
			// create leaf
			return new KDNode(primitives, null, null, 0, 0);
		} else {
			double d = calcMean(primitives, axis);
			while((primitive = primitives.poll()) != null) {
				pos = primitive.inHalfSpace(d, axis);
				switch (pos) {
				case BOTH:
					front.add(primitive);
					back.add(primitive);
//					System.out.print(" both");
					break;
				case FAR:
					back.add(primitive);
//					System.out.print(" far");
					break;
				case NEAR:
					front.add(primitive);
//					System.out.print(" near");
					break;
				default:
					System.err.println("\t >> can't add primitive ...");
					break;
				}
			}
			/*
			// get normal for splitting plane
			switch (axis) {
			case 0:
				normal = new double[]{1, 0 ,0};
				break;
			case 1:
				normal = new double[]{0, 1 ,0};
				break;
			case 2:
				normal = new double[]{0, 0 ,1};
				break;
			default:
				normal = new double[]{1, 0 ,0};
				System.err.println("\t >> not right axis ...");
				break;
			}
			// plane not for drawing -> material := null
			p = new Plane(normal, Math.abs(mean), null);
			// create node
			 */
			return new KDNode(null, createKDTree(front, depth+1), createKDTree(back, depth+1), axis, d);
		}
	}
	
	public Primitive travers (double[] pos, double[] ray, double length, double[] intersection) {
		Primitive prim = null;
		
		// if node is leaf check all primitives in leaf
		if(isleaf()) {
			double t, tmin = Double.MAX_VALUE;
			Primitive primitive = null;
			for (Primitive p : primitives) {
				t = p.intersection(pos, ray);
				if (t != Double.NaN && t >= RaytracerImage.tMin && t < tmin && t <= length) {
					tmin = t;
					primitive = p;
				}
			}
			
			if (primitive != null) {
				if (intersection != null) {
					intersection[0] = pos[0] + ray[0] * tmin;
					intersection[1] = pos[1] + ray[1] * tmin;
					intersection[2] = pos[2] + ray[2] * tmin;
				}				
			}
			
			return primitive;
			
			/*
			double t, tClosest = Double.MAX_VALUE;
			int iClosest = -1;
			Primitive prim_tmp = null;
			Iterator<Primitive> it = primitives.iterator();
			while(it.hasNext()) {
				prim = it.next();
				t = prim.intersection(pos, ray);
				if (t != Double.NaN && t >= RaytracerImage.tMin && t < tClosest && t <= length) { // intersecting and on positive side of ray and closer than closest primitive so far				
					tClosest = t;
					iClosest = primitives.indexOf(prim);
					prim_tmp = prim;
				}
			}
			if (iClosest > -1) { // intersection found
				if (intersection != null) {
					intersection[0] = pos[0] + ray[0] * tClosest;
					intersection[1] = pos[1] + ray[1] * tClosest;
					intersection[2] = pos[2] + ray[2] * tClosest;
				}
				return prim_tmp;
			} else {
				return null;
			}
			*/
		} else {
			if (pos[axis] > d) {
				prim = front.travers(pos, ray, length, intersection);
				if (prim == null) {
					prim = back.travers(pos, ray, length, intersection);
				}
			} else {
				prim = back.travers(pos, ray, length, intersection);
				if (prim == null) {
					prim = front.travers(pos, ray, length, intersection);
				}				 
			}
			
			
			/*
			double angle = Geometry.dotProduct(plane.getNormal(pos), ray);
			if(angle < 0) {
				prim = front.travers(pos, ray, length, intersection);
				if(prim == null) {
					prim = back.travers(pos, ray, length, intersection);
				}
			} else {
				prim = back.travers(pos, ray, length, intersection);
				if(prim == null) {
					prim = front.travers(pos, ray, length, intersection);
				}
			}
			*/
		}
		return prim;
	}
	
	public void printLeafs() {
		if (isleaf()) {
			System.out.println(primitives.size());
		} else {
			System.out.println("NODE");
			front.printLeafs();
			back.printLeafs();
		}
	}
	
	private static double calcMean(LinkedList<Primitive> pr, int axis) {
		double mean = 0;
		int count = 0;
		double[] p;
		Iterator<Primitive> it = pr.iterator();
		while(it.hasNext()) {
			p = it.next().getPostion();
			mean += p[axis];
			count++;
		}
		return mean/count;
	}
}
